In this context the adjective “continuous” when applied to a channel and in particular to its impulse response, means continuous in the time-domain, or continuous-time, i.e. a varying quantity whose domain, in this case the time, is a continuum, e.g. a connected interval of real numbers. In other words, the function's domain is an uncountable set. The impulse response function itself need not be continuous. To contrast, the impulse response of a discrete-time channel has a countable domain, like natural numbers. The impulse response of a discrete-time channel can be obtained by sampling the impulse response of a continuous-time channel.
In each of the above cited applications, the continuous channel is unknown although it is known that it is sparse in time, i.e. it consists of few well localised signals, for example due to echoes in an acoustic room. An example of a continuous sparse channel is a channel whose impulse response h(t) can be modeled as a linear combination of several Diracs, i.e.
                              h          ⁡                      (            t            )                          =                              ∑                          k              =              1                        K                    ⁢                                          ⁢                                    c              k                        ⁢                          δ              ⁡                              (                                  t                  -                                      t                    k                                                  )                                                                        (        1        )            where {ck}k=1K and {tk}k=1K are some unknown parameters. K is the sparsity of the channel.
In the context of the one embodiment of the invention the function h(t) is the impulse response of the continuous-time channel. Since a channel can be modeled as a filter, in this context we also refer h(t) as the filter that models the continuous-time channel. Similar considerations are valid for the other cited channel, e.g. the discrete-time channel. An example of an impulse response of the continuous-time channel h(t) is illustrated in FIG. 3, which will be discussed later.
It is often wanted to learn this unknown continuous sparse channel by building an estimate of this filter h(t). Since the channel is changing in time, it is often necessary to modify this channel iteratively in order to adapt this estimate to the variations of the continuous sparse channel in time.
A possible system comprising an automatic and adaptive channel estimate is illustrated in FIG. 1, which represents a scenario involving hands-free telephony in an acoustic and close room 1. In this figure, s1 represents a known voice signal coming from a party at a remote side of the conversation and played back with a loudspeaker 2. A speaker 4 is speaking by using the microphone 6; s2 represents the acoustic signal which is picked up by the microphone 6. However the microphone 6 picks up also a distorted copy of s1: the distortion is due to the room reverberations and can be modeled as the convolution between s1 and an unknown filter H, indicated with the reference 100 and corresponding to the acoustic channel between the source s1 and the microphone 4. In other words the microphone 6 measures both the speaker voice s2 and the result of above convolution:s2+s1*H  (2)
The goal of the system is to transmit to the party at the remote side only the signal s2, so that this party will not hear the echoes s1*H of her/his own voice. This task is also known as “acoustic echo cancellation” and it is achieved by using an adaptive filter Ĥ, indicated with the reference 400, which represents an estimate of the unknown filter H 100.
The signal s1 is also the input of the filter Ĥ 400 and its output is indicated by ŝ1. The closer the filter Ĥ to the unknown filter H, the more ŝ1 is equal to s1. For this reason ŝ1 is subtracted (reference 50) from the output of the microphone given by the above expression (2): in the ideal case, i.e. in the case wherein the filter Ĥ exactly reproduced the unknown filter H(s2+s1*H)−ŝ1=s2+s1*H−s1*ĤH=Ĥ=s2  (3)
The arrow of the filter Ĥ 400 in FIG. 1 indicates that it can be iteratively modified in order to adapt Ĥ to temporal variations of H.
The example of FIG. 1 has been introduced for focusing the problem. However the scope of one embodiment of the invention is not limited to the described example: as already mentioned, the man skilled in the art can imagine other scenarios in which it is necessary to adaptively learn a sparse impulse response of a continuous, almost shift-invariant channel.
Generally speaking, a linear channel that is “almost” shift-invariant, i.e. that is slowly varying in time, is an example of a continuous—and unknown—channel for which it is useful to learn its sparse impulse response. How “slow” a channel varies is relative to the tracking speed of the channel identification methods. In general, the channel should remain roughly constant within N taps, where N is the number of steps taken by an adaptive method for converging to a solution.
Computing a filter estimate Ĥ is based on linear system identification, which is a classical and well-studied subject. A known method for learning a general sparse impulse response h(t) of a continuous channel can be summarized as follows. x(t) and y(t) are the input and output signal of the unknown continuous channel, respectively. The input x(t) is supposed to be band-limited, so that x(t) and y(t) can be converted into the discrete domain by sampling them at or above the Nyquist rate.
Since the sampling process is alias-free, the resulting discrete signals—denoted by x[n] and y[n] respectively—are also related by a linear shift-invariant system, i.e.y[n]=(x*hd)[n]  (4)
The discrete filter hd [n] above either completely determines the original continuous-time impulse response h(t) if the latter is band-limited and has a bandwidth below that of x(t), or is a low-pass approximation of h(t). In practice, hd[n] is usually approximated by a finite impulse response (FIR) filter with N taps, where N is chosen to be large enough to retain most of the energy of hd[n]. In other words after sampling, the discrete filter hd [n] is approximated by an FIR model, whose length, N, must be large enough to capture the longest possible delay in the system. More specifically:
                    N        ≈                                            max              k                        ⁢                          t              k                                T                                    (        5        )            where T is the sampling interval. N is generally much larger than the number of delays K that make up the system itself.
This finite-order system can then be learned from x[n] and y[n] by using standard adaptive filtering techniques, such as the least mean squares (LMS) algorithm.
Despite its widespread and successful use in practice for learning general linear time-invariant systems, the traditional approach described above is computationally expensive, since all the N filter taps have to be determined. Moreover the bandwidth of the input signal x(t) needs to be limited, so that x(t) and y(t) can be converted into the discrete domain by sampling them at or above the Nyquist rate. However there are wide classes of very common signals, including stream of Dirac pulses, bi-level signals, piecewise polynomial signals, etc. which are not band-limited and which cannot be used for estimating the channel with this known method. An example of a system using such no band-limited signals is the CDMA.
Even if the signals are band-limited, their bandwidth is sometime very large, so that the current methods requires fast, expensive and power-consuming A/D converter, fast digital circuits and a waste storage place for storing the digitized signals while fulfilling the Nyquist condition. Examples of signals with a large bandwidth that makes them impracticable for the above mentioned methods include UWB signals.
Moreover the known standard adaptive filtering techniques are not efficient, since when either the input signal x(t) or the channel noise is not white, there is no possibility to select the frequency band of the input signal x(t) with the highest SNR (Signal to Noise Ratio).
Known algorithm which adaptively obtains the impulse response of the filter Ĥ 400 include the Frequency Least Mean Square (FLMS), which operates in the frequency-domain, the Recursive Least Square (RLS) and the reweighted zero attracting method (RZA), both operating in the time-domain. An example of RZA method is given by Y. Chen, Y. Gu, and A. O. Hero, “Sparse LMS for system identification,” in Proc. IEEE Int. Conf Acoust., Speech, and Signal Proc., Taipei, 2009. Another LMS sparsity-exploiting method operating in the time domain is given by R. K. Martin, W. A. Sethares, R. C. Williamson, and C. R. Johnson, “Exploiting sparsity in adaptive filters,” IEEE Trans. Signal Process., vol. 50, no. 8, pp. 1883-1894, August 2002.
If for comparison purposes the parameters of each algorithm are made equal when possible, the known FLMS, compared to the RLS and the RZA, has the highest Mean-Squared output Error (MSE). The RLS is not efficient to track a change of the unknown filter taps. The RZA is efficient in tracking these changes, it presents a MSE better than a classical FLMS but it is computationally complex and requires a sampling rate above the Nyquist system, i.e. the convergence rate is quite low. Moreover RZA does not handle well the modelling of the sparsity off of the sampling grid since it assume that the discrete channel is exactly K-sparse. However, if the continuous dirac delta (t−t_k) falls on a fractional number (i.e. off the discrete grid), one can see a sinc function in the discrete domain, which is not exactly sparse. Finally RLS and RZA methods are computationally less efficient than frequency domain methods, if block-based processing is used.
WO10083321 describes a method for reconstructing a pair of signals, wherein the first signal is linked to the second signal by an unknown but sparse filter. In this case the sparseness information is used for reconstructing the two signals, but not the filter itself Moreover the method assumes that the unknown channels are constant over time, i.e. it cannot track slowly-varying channels.
A method and an apparatus for adaptively learning a sparse impulse response of a continuous channel which does not necessarily require a band-limited input signal x(t) and with a lower computational complexity than known methods are needed.
A method and an apparatus for adaptively learning a sparse impulse response of a continuous channel which are more efficient in the case when either the input signal x(t) or the channel noise is not white are also needed.
A new FLMS method which is efficient to track a change of the unknown filter taps, which presents a MSE better than a classical FLMS, which is more versatile and less computationally complex than other known method is also needed.